package leetcode.动态规划.simple;

/**
 * @author wangmaolin1
 * @date 2022/1/9 下午10:53
 */
public class _338比特位计数 {

    //给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
    public int[] countBits(int num) {
        int[] result = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            if ((i & 1) == 0) {
                //1. 偶数x 的1的个数和 x/2 的1的个数相等
                result[i] = result[i >> 1];
            } else {
                // 2.奇数的1的个数一定比前一个偶数的1的个数多1
//                result[i] = result[i - 1] + 1;
                //2结合1，奇数时，1的个数也和 x/2的偶数的个数相等
                //因此转化为:
                result[i] = result[i >> 1] + 1;
            }
        }
        return result;
    }

    public int[] countBitsV2(int n) {
        int[] bits = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            //第一种方式再优化，最后的1为奇数是才 添加，因此直接通过i & 1的方式判断是否为奇数，i & 1=1为奇数，i & 1=0为偶数
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }

}
